#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void swap(int* as, int* aq)
{
	int tmp = *as;
	*as = *aq;
	*aq = tmp;
}
void charu(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
int sanshuquzhong(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] <a[right])
	{
		if (a[mid] > a[right])
		{
			return right;
		}
		else if (a[mid] < a[left])
		{
			return left;
		}
		else
		{
			return mid;
		}
	}
	else
	{
		if (a[mid] >a[left])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
}
void kuaisu(int* a, int left, int right)
{
	if (left >= right)
	{
		return 0;
	}
	if (right - left + 1 < 10)
	{
		charu(a + left, right - left + 1);
	}
	else
	{
		int mid = sanshuquzhong(a, left, right);
		swap(&a[left], &a[mid]);
		int key =left;
		int begin = left;
		int end = right;
		int keng = left;
		while (begin < end)
		{
			while (begin<end && a[end]>=a[key])
			{
				end--;
			}
			a[keng] = a[end];
			keng = end;
			while (begin<end && a[begin]<=a[key])
			{
				begin++;
			}
			a[keng] = a[begin];
			keng = begin;
		}
		 a[keng]=a[key];
		 key = begin;
		kuaisu(a, left, key - 1);
		kuaisu(a, key+1, right);
	}

}
int main()
{
	int arr[] = { 123,54,2353,46,56,3765,8,37568,769,768,98,959,59,698,06,89,72546,1326,13465,1 };
	kuaisu(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	
	return 0;
}